import pygame

class Cat(object):
    def __init__(self, row, line, board):
        self.row = row
        self.line = line
        self.board = board
        self.debug = True
        

        self.visited = []
        for j in range(len(board)):
            t = []
            for i in range(len(board[0])):
                t.append(0)

            self.visited.append(t)

    def set_pos(self, pos):
        self.line = pos[0]
        self.row = pos[1]

    # 判断是否到达地图边界：如果x,y在地图边界上就返回True，否则返回False
    def reach_border(self, x, y):
        if x == 0:
            return True
        if y == 0:
            return True
        if x == len(self.board[0]) - 1:
            return True
        if y == len(self.board) - 1:
            return True

        return False

    def get_path(self, x, y):
        print(self.visited)
        r = [(x, y)]
        prev = self.visited[y][x]
        print("prev of (%d, %d) is %s" % (x, y, prev))
        r.append(prev)
        while(prev != -1):
            print(prev)
            x, y = prev
            prev = self.visited[y][x]
            r.append(prev)

        return r 
        
    def next_step(self):
        print("BFS start, board is %s" % (self.board))

        for (i, r) in enumerate(self.board):
            for (j, e) in enumerate(r):
                self.visited[i][j] = 0
        
        self.queue = []
        self.queue.append((self.line, self.row))
        self.visited[self.row][self.line] = -1

        while self.queue:
            print(f"current queue is {self.queue}")
            x, y = self.queue.pop(0)

            steps = [(-1, 0), (1, 0)]
            if (y & 1 == 0):
                steps.extend([(-1, -1), (0, -1), (-1, 1), (0, 1)])
            else:
                steps.extend([(1, -1), (0, -1), (1, 1), (0, 1)])

            for dx, dy in steps:
                nx = x + dx
                ny = y + dy
                if (self.board[ny][nx] == 0 and self.visited[ny][nx] == 0):
                    if self.debug:
                        print("ny = %d, nx = %d" % (ny, nx))

                    self.visited[ny][nx] = (x, y)
                    if self.reach_border(nx, ny):
                        return self.get_path(nx, ny)
                    self.queue.append((nx, ny))

    def draw(self, screen, color, padding, gwidth, gheight, r):
        pygame.draw.circle(screen, color,
            (self.line * gwidth + gwidth // 2 + (padding if (self.row & 1) == 1 else 0),
            self.row * gheight + gheight // 2), r)
